﻿#include <iostream>
#include <queue>
#include "Graph.h"

static void search(const Graph* graph, GraphNode* startNode)
{
    unordered_set<GraphNode*> appearNodes;
    queue<GraphNode*> nodeQueue;
    appearNodes.insert(startNode);
    nodeQueue.push(startNode);

    while (!nodeQueue.empty())
    {
        auto frontNode = nodeQueue.front();
        printf("%c->", frontNode->value);
        nodeQueue.pop();
        for (auto nodeIterator = frontNode->nextNodes.begin(); nodeIterator != frontNode->nextNodes.end(); nodeIterator++)
        {
            auto nextNode = *nodeIterator;
            if (appearNodes.find(nextNode) != appearNodes.end()) continue;

            nodeQueue.push(nextNode);
            appearNodes.insert(nextNode);
        }
    }

    printf("\n");
}

/**
 * 宽度优先遍历
 * 1. 利用队列实现
 * 2. 从源节点开始依次按照宽度进队列，然后弹出
 * 3. 每弹出一个点，把该节点所有没有进入过队列的邻接点放入队列
 * 4. 直到队列变空
 */
int main_BreadthFirstSearch()
{
    int matrix[][3] = {
        {'a', 'b', 6},
        {'a', 'c', 1},
        {'a', 'd', 5},
        {'b', 'c', 5},
        {'b', 'e', 3},
        {'c', 'd', 5},
        {'c', 'e', 6},
        {'c', 'f', 4},
        {'d', 'f', 2},
        {'e', 'f', 6},
    };

    int* pMatrix = matrix[0];
    auto graph = Graph::generate(&pMatrix, sizeof(matrix) / sizeof(int) / 3, 3, false);
    search(graph, graph->nodes.at('a'));
    delete(graph);
    return 0;
}